package strings;

/**
 * 给定一个字符串，逐个翻转字符串中的每个单词。
 *
 *  
 *
 * 示例 1：
 *
 * 输入: "the sky is blue"
 * 输出: "blue is sky the"
 * 示例 2：
 *
 * 输入: "  hello world!  "
 * 输出: "world! hello"
 * 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * 示例 3：
 *
 * 输入: "a good   example"
 * 输出: "example good a"
 * 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *  
 *
 * 说明：
 *
 * 无空格字符构成一个单词。
 * 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 * 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class ReverseWords {
    public String reverseWords(String s) {
        if(s == null){
            return null;
        }
        if(s.trim().length() == 0){
            return s.trim();
        }
        String reversed = reverse(s);
        StringBuilder sb = new StringBuilder(reversed);
        StringBuilder result = new StringBuilder();
        int start = 0;
        int end = 0;
        boolean lastSpace = false;
        while(end < sb.length()){
            if(sb.substring(end, end +1).equals(" ")){
                if(!lastSpace) {
                    result.append(reverse(sb.substring(start, end)));
                    result.append(" ");
                    start = end + 1;
                }
                lastSpace = true;
            } else {
                lastSpace = false;
            }
            end ++;
        }
        if(start < end){
            result.append(reverse(sb.substring(start, end)));
        }
        return result.toString();
    }

     private String reverse(String s){
        StringBuilder sb = new StringBuilder(s.trim());
        return sb.reverse().toString().trim();
     }

     public static void main(String[] args){
        String s = (new ReverseWords()).reverseWords("  hello world!  ");
        System.out.println(s);
     }
}
